#include <iostream>
#include <vector>
#include <algorithm>

// 使用别名
typedef int Rank;

// 归并所需的辅助向量
std::vector<int> aux;

// 归并排序的函数
void merge(std::vector<int>& vec, Rank lo, Rank mid, Rank hi) {
    Rank i = lo, j = mid + 1;
    for (Rank k = lo; k <= hi; k++) {
        aux[k] = vec[k];  // 复制元素到辅助数组
    }
    for (Rank k = lo; k <= hi; k++) {
        if (i > mid) vec[k] = aux[j++];  // 左半部分用尽，取右半部分元素
        else if (j > hi) vec[k] = aux[i++];  // 右半部分用尽，取左半部分元素
        else if (aux[j] < aux[i]) vec[k] = aux[j++];  // 右半部分当前元素小于左半部分当前元素，取右半部分元素
        else vec[k] = aux[i++];  // 左半部分当前元素小于或等于右半部分当前元素，取左半部分元素
    }
}

void mergeSort(std::vector<int>& vec, Rank lo, Rank hi) {
    if (hi - lo < 1) return;  // 元素数量小于2，无需排序
    Rank mid = (lo + hi) / 2;
    mergeSort(vec, lo, mid);  // 归并排序左半部分
    mergeSort(vec, mid + 1, hi);  // 归并排序右半部分
    merge(vec, lo, mid, hi);  // 归并结果
}

int main() {
    std::vector<int> SortedVector41 = { 6, 3, 2, 7, 1, 5, 8, 4 };
    aux.resize(SortedVector41.size());  // 初始化辅助向量的空间

    // （1）在区间[0,8)进行归并排序
    mergeSort(SortedVector41, 0, SortedVector41.size() - 1);
    std::cout << "Sorted vector for range [0, 8): ";
    for (int num : SortedVector41) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // （2）在区间[0,7)进行归并排序
    std::vector<int> SortedVector42 = { 6, 3, 2, 7, 1, 5, 8, 4 };
    mergeSort(SortedVector42, 0, SortedVector42.size() - 2);
    std::cout << "Sorted vector for range [0, 7): ";
    for (int num : SortedVector42) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // （3）在区间[3,6)进行归并排序
    std::vector<int> SortedVector43 = { 6, 3, 2, 7, 1, 5, 8, 4 };
    mergeSort(SortedVector43, 3, 5);
    std::cout << "Sorted vector for range [3, 6): ";
    for (int num : SortedVector43) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}